package org.algorithm.biubiu.wheel_1.回溯算法;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;

/**
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * <p>
 * <p>
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * <p>
 * <p>
 * 链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/        17
 */
public class $4月26日$电话号码组合 {


    HashMap<Character, String> phoneMap = new HashMap<Character, String>() {
        {
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }
    };


    List<String> res = new ArrayList();
    String digits;
    public List<String> letterCombinations(String digits) {

        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        this.digits = digits;
        backTrack(0);
        return res;
    }


    List<Character> cur = new ArrayList();
    public void backTrack(int step){
        if(cur.size()==digits.length()){
            res.add(listToString(cur));
            return;
        }

        String data = phoneMap.get(digits.charAt(step));
        for(int j=0;j<data.length();j++){
            cur.add(data.charAt(j));
            backTrack(step+1);
            cur.remove(cur.size()-1);
        }

    }


    public String listToString( List<Character> cur){
        String s = "";
        for(Character e:cur){
            s +=e;
        }
        return s;

    }
}
